import java.util.*;

public class 课程表II {
    //https://leetcode.cn/problems/course-schedule-ii/description/
    //拓扑排序模板题
    //调用队列
    public int[] findOrder1(int n, int[][] pp) {
        //入度的数量
        int[] in = new int[n];
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        for(int[] p : pp){
            graph.get(p[1]).add(p[0]);
            in[p[0]]++;
        }
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if(in[i] == 0){
                q.add(i);
            }
        }
        List<Integer> l = new ArrayList<>();

        while(!q.isEmpty()){
          int t = q.poll();
          l.add(t);
            for(int num : graph.get(t)){
                if(--in[num] == 0){
                   q.add(num);
                }
            }
        }
        for (int i = 0; i < n; i++) {
            if (in[i] != 0) {
                return new int[]{};
            }
        }
        int[] ans = new int[l.size()];
        int size = 0;
        for (int i : l){
            ans[size++] = i;
        }
        return ans;
    }
    //手写队列
    public int[] findOrder(int n, int[][] pp) {
        //入度的数量
        int[] in = new int[n];
        //邻接链表
        List<List<Integer>> graph = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        for(int[] p : pp){
            graph.get(p[1]).add(p[0]);
            in[p[0]]++;
        }
        //书写队列
        int l = 0;
        int r = 0;
        int[] queue = new int[n];
        //入度为0的先遍历
        for (int i = 0; i < n; i++) {
            if(in[i] == 0){
                queue[r++] = i;
            }
        }
        int cnt = 0;
        //不断消除入度的, 找到入度为0的
        while(l < r){
            int cur = queue[l++];
            cnt++;
            for(int num : graph.get(cur)){
                if(--in[num] == 0){
                    queue[r++] = num;
                }
            }
        }

        return cnt == n ? queue : new int[]{};
    }
}
